package strStr;

import java.util.Arrays;

public class Solution {
//    public int strStr(String haystack, String needle) {
//        // 枚举
//        int len = needle.length();
//        for (int i = 0; i + len< haystack.length(); i++) {
//            if( check(i,haystack,needle) )return i;
//        }
//        return -1;
//    }
//    private boolean check(int i,String haystack,String needle) {
//        return haystack.substring(i,i+needle.length()).equals(needle);
//    }

    public int strStr(String haystack, String needle) {
        // KMP算法

        // 前缀表 模式串的最长相等的前缀和后缀的长度
        // 前缀串 --- 不包含尾字符的字符串 (比如aabaaf前缀串 = [a,aa,aab,aaba,aabaa])
        // 后缀串 --- 不包含首字符的字符串 (比如aabaaf后缀串 = [f,af,aaf,baaf,abaaf])
        // 前缀表 --- 最长相等的前缀和后缀的长度 a      0   (前缀和后缀字串都为空)
        //                                aa     1   (前缀[a],后缀[a])
        //                                aab    0   (前缀[a,aa],后缀[b,ab])
        //                                aaba   1   (前缀[a,aa,aab],后缀[a,ba,aba])
        //                                aabaa  2   (前缀[a,aa,aab,aaba],后缀[a,aa,baa,abaa])
        //                                aabaaf 0   (前缀[a,aa,aab,aaba,aabaa],后缀[f,af,aaf,baaf,abaaf]);
        // aabaaf的前缀表
        // 010120

        // 文本串aabaabaaf
        // 模式串aabaaf
        //  a a b a a b a a f
        //        a a b a a f
        // 求next数组
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] next = getNext(needle);
        for (int i = 0,j = 0; i < n; i++) {
            while (j>0&&haystack.charAt(i)!=needle.charAt(j)) {
                j = next[j-1];
            }
            if(haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if(j==m) {
                return i - m + 1;
            }
        }
        return -1;
    }
    // 求next数组
    private int[] getNext(String s) {
        int[] next = new int[s.length()];
        // i表示前缀字符串和后缀字符串最长相等字串的位置
        int j = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j>0&&s.charAt(i)!=s.charAt(j)) {
                j = next[j-1];
            }
            if(s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
